package main.java;
import java.util.Arrays;

public class HeapSort {
    /**
     * 构建大顶堆
     * 在已知左右为大根堆的情况下构建大根堆
     */
    public static void adjustHeap(int[] a,int i, int len){
        int temp;
        temp = a[i];
        for (int j = 2*i; j < len ; j=j*2) {
            if (j+1<len && a[j]<a[j+1])
                ++j; //j为关键字中较大记录的下标
            if (temp>=a[j])
                break;//恰好保持了大根堆性质
            a[i]=a[j]; //将较大的根节点交换上去
            i=j; //新的根
        }
        a[i]=temp;
    }
    public static void heapSort(int[] a) {
        int i;
        for (i = a.length / 2 - 1; i >= 0; i--) {// 构建一个大顶堆
            adjustHeap(a, i, a.length - 1);
        }
        for (i = a.length - 1; i >= 0; i--) {// 将堆顶记录和当前未经排序子序列的最后一个记录交换
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            adjustHeap(a, 0, i - 1);// 将a中前i-1个记录重新调整为大顶堆
        }
    }

    public static void main(String[] args) {
        int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}